全排列II: https://leetcode-cn.com/problems/permutations-ii/

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
           在全排列 的基础上，要加上对 重复的数值导致的结果 重复的剪枝，具体看视频分析
        """
        rst = []
        used = [False] * len(nums)
        # 对列表进行排序， 使相同的元素，在一起
        nums.sort()
        def dfs(arr):
            if len(arr) == len(nums):
                rst.append(arr[:])
                return 
            
            for i in range(len(nums)):
                # 1. 元素去重
                if used[i] == True:
                    continue
                # 2. 结果去重。 当当前 值 等于 上一个值时，说明当前的 递归所有结果 与 上一元素重复，整个剪枝（跳过）
                # 这里要注意最后的条件判断。 i - 1位置的元素，必须为 False， 也就是说明 前面的元素已经递归使用过了，而不是正在使用，结合视频，好好理解。没有这个条件，得到的将是0. 与全排列的区别，就在于这个 if 判断 和 对列表排序，再次剪枝~！！！
                if i > 0 and nums[i - 1] == nums[i] and not used[i-1]:
                    continue
                used[i] = True
                arr.append(nums[i])
                dfs(arr)
                # 列表是可变对象， 回溯时，要手动清除这次添加的元素
                arr.pop()
                used[i] = False

        dfs([])
        
        return rst